#define  _CRT_SECURE_NO_WARNINGS 1
#define  _CRT_SECURE_NO_WARNINGS 1
#include<string.h>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<time.h>
struct stu
{
	char name[20];
	int cz;
};

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

int cmp_long_long(const void* e1, const void* e2)
{
	long long ret = *(long long*)e1 - *(long long*)e2;
	if (ret > 0) return 1;
	else return -1;
}

int cmp_struct_string(const void* e1, const void* e2)
{
	int a = strcmp(((struct stu*)e1)->name, ((struct stu*)e2)->name);
	if (a == 0)
		return (((struct stu*)e1)->cz - ((struct stu*)e2)->cz);
	else return a;
}

int cmp_float(const void* e1, const void* e2)
{
	float ret = *(float*)e1 - *(float*)e2;
	if (ret > 0 && ret < 0.000001) return 0;
	else if (ret > 0) return 1;
	else return -1;
}

int cmp_double(const void* e1, const void* e2)
{
	double ret = *(double*)e1 - *(double*)e2;
	if (ret > 0 && ret < 0.000001) return 0;
	else if (ret > 0) return 1;
	else return -1;
}

int cmp_struct_int(const void* e1, const void* e2)
{
	return (((struct stu*)e1)->cz - ((struct stu*)e2)->cz);
}


void swap(char* a, char* b, int size)
{
	assert(a && b);
	char* temp = (char*)malloc(size);
	//assert(temp);
	if (temp == NULL)
		exit(EXIT_FAILURE);
	memcpy(temp, a, size);
	memcpy(a, b, size);
	memcpy(b, temp, size);
	free(temp);
	temp = NULL;
}

void my_qsort_kh(void* base, int size, int nitems, int(*cmp)(const void* e1, const void* e2))//核心程序
{
	assert(base && cmp && size > 0);
	if (nitems <= 1) return;
	srand((unsigned int)time(NULL));
	char* pivot = (char*)base + rand() % nitems * size;
	char* i = (char*)base;
	char* j = (char*)base + size * (nitems - 1);
	int cnt_i = 0;
	int cnt_j = 0;
	while (i < j)
	{
		while (cmp(j, pivot) >= 0 && i < j)
		{
			j -= size;
			cnt_j++;
		}
		swap(pivot, j, size);
		pivot = j;
		while (cmp(i, pivot) <= 0 && i < j)
		{
			i += size;
			cnt_i++;
		}
		swap(i, pivot, size);
		pivot = i;
	}
	my_qsort_kh(base, size, cnt_i, cmp);
	my_qsort_kh(i + size, size, cnt_j, cmp);
}

void test1_int()
{
	int arr[10] = { 3,2,1,4,5,7,8,0,9,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort_kh(arr, sizeof(arr[0]), sz, cmp_int);
	for (int k = 0; k < 10; k++) printf("%d ", arr[k]);
}

void test2_struct_string()
{
	struct stu s[] = { {"zhangsan",50},{"zhangsan",30},{"zhangsan",90},{"zhangwu",20} ,{"lia",30},{"waw",90} };
	int sz = sizeof(s) / sizeof(s[0]);
	my_qsort_kh(s, sizeof(s[0]), sz, cmp_struct_string);
}

void test3_float()
{
	float f[10] = { 1.2f,0.6f,9.5f,0.02f,4.03f,9.21f,5.0f,8.41f,1.11f,2.11f };
	int sz = sizeof(f) / sizeof(f[0]);
	my_qsort_kh(f, sizeof(f[0]), sz, cmp_float);
	for (int k = 0; k < 10; k++) printf("%f ", f[k]);
}

void test4_double()
{
	double d[10] = { 1.2,0.6,9.5,0.02,4.03,9.21,5.0,8.41,1.11,2.11 };
	int sz = sizeof(d) / sizeof(d[0]);
	my_qsort_kh(d, sizeof(d[0]), sz, cmp_double);
	for (int k = 0; k < 10; k++) printf("%lf ", d[k]);
}

void test5_long_long()
{
	long long arr[8] = { 5555555555555555555,2222222222222222222,4444444444444444444,6666666666666666666,7777777777777777777,8888888888888888888,0,3333333333333333333 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort_kh(arr, sizeof(long long), sz, cmp_long_long);
	for (int k = 0; k < 8; k++) printf("%lld ", arr[k]);
}


void test6_struct_int()
{
	struct stu s[] = { {"zhangsan",50},{"lisi",30},{"wangwu",90},{"zhangwu",20} ,{"lia",30},{"waw",90} };
	int sz = sizeof(s) / sizeof(s[0]);
	my_qsort_kh(s, sizeof(s[0]), sz, cmp_struct_int);
}



int main()//样例测试
{
	//test1_int();
	//test2_struct_string();
	//test3_float();
	//test4_double();
	//test5_long_long();
	//test6_struct_int();
	return 0;
}















//#include<stdio.h>
//#include<stdlib.h>
//#include<time.h>
//#define N 1000
//int arr1[N];
//void rand_arr_kh()//生成随机数组
//{
//	srand((unsigned int)time(NULL));
//	for (int i = 0; i < N; i++)
//		arr1[i] = rand() % 100;
//}
//int main()
//{
//	int a = 0;
//	rand_arr_kh();
//	for (a = 0; a < N; a++) printf("%d ", arr1[a]);
//	printf("\n--------------------------------------------------------------------------------------------------------------------\n");
//	my_qsort_kh(arr1, sizeof(arr1[0]), N, cmp_int);
//	for (a = 0; a < N; a++) printf("%d ", arr1[a]);
//	printf("\n--------------------------------------------------------------------------------------------------------------------\n");
//	return 0;
//}